using System;

namespace GraphSpace
{
	public class Graphgenerator<TV, TE> where TV : Knoten, new() where TE : Kante, new()
	{

		public Graphgenerator ()
		{
		}

		public static Graph<TV,TE> generiere_Zufall (int n, int m)
		{
			Graph<TV, TE> G = new Graph<TV, TE> ();
			for (int i = 0; i < n; i++) {
				G.neuerKnoten (i);
			}
			
			for (int i = 0; i < m; i++) {
				bool gültig = false;
				while (!gültig) {
					Random zufall = new Random (i + System.DateTime.Now.Millisecond);
					int e1 = zufall.Next (0, n);
					int e2 = zufall.Next (0, n);
					if (G.neueKante (e1, e2, 0.0))
						gültig = true;
				}
			}
			
			return G;
		}

		public static Graph<TV, TE> generiere_Eulerkreis (int n, int m)
		{
			Graph<TV, TE> G = generiere_Kreis(n);
			
			while (m > 0) {
				Random zufall = new Random (m + System.DateTime.Now.Millisecond);
				int s = zufall.Next (0, n);
				int x = s;
				int y;
				
				do {
					y = zufall.Next (0, n);
					if (y != x) {
						G.neueKante (x, y, 0.0);
						m--;
						x = y;
					}
				} while (y != s);
			}
			
			return G;
		}

        public static Graph<DijkstraKnoten, Kante> generateEuklidGraph(int laenge, int otherNodes, int Kanten)
        {
            Graph<DijkstraKnoten, Kante> G = new Graph<DijkstraKnoten, Kante>();
            Random rand = new Random();

            for (int i = 0; i < laenge; i++)
            {
                DijkstraKnoten node = new DijkstraKnoten(i, int.MaxValue, null, int.MaxValue, 0, i);
                G.neuerKnoten(node);
            }
            for (int i = 0; i < laenge-1; i++)
            {
                G.neueKante(i, i + 1, 1);
            }

            for (int i = 0; i < otherNodes; i++)
            {
                DijkstraKnoten node = new DijkstraKnoten(i + laenge, int.MaxValue, null, int.MaxValue, rand.Next(100), rand.Next(100));
                G.neuerKnoten(node);
            }

            for (int i = 0; i < Kanten; i++)
            {
                int von = rand.Next(G.V.Count - 1);
                int nach = rand.Next(G.V.Count - 1);
                while (von == nach)
                {
                    nach = rand.Next(G.V.Count - 1);
                }
                DijkstraKnoten vonK = G.V[von];
                DijkstraKnoten nachK = G.V[nach];
                G.neueKante(von, nach, Math.Abs(vonK.x - nachK.x) + Math.Abs(vonK.y - nachK.y));
            }

            return G;
        }

		public static Graph<TV, TE> generiere_Kreis (int n)
		{
			Graph<TV, TE> G = new Graph<TV, TE> ();
			for (int i = 0; i < n; i++)
				G.neuerKnoten (i);
			for (int i = 0; i < n - 1; i++)
				G.neueKante (i, i + 1, 0.0);
			G.neueKante (n - 1, 0, 0.0);
			
			return G;
		}
	}
}
